﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Aeon.Emulator.Memory
{
    /// <summary>
    /// Simple memory allocator for reserving regions of conventional memory.
    /// </summary>
    internal sealed class MetaAllocator
    {
        #region Private Fields
        /// <summary>
        /// Tracks memory allocations.
        /// </summary>
        private readonly LinkedList<Allocation> allocations = new LinkedList<Allocation>();
        #endregion

        #region Constructors
        /// <summary>
        /// Initializes a new instance of the MetaAllocator class.
        /// </summary>
        public MetaAllocator()
        {
            Clear();
        }
        #endregion

        #region Public Methods
        /// <summary>
        /// Clears all allocations and resets the allocator to its initial state.
        /// </summary>
        public void Clear()
        {
            lock(this.allocations)
            {
                this.allocations.Clear();
                this.allocations.AddLast(new Allocation(0, PhysicalMemory.ConvMemorySize >> 4, false));
            }
        }
        /// <summary>
        /// Reserves a new block of memory.
        /// </summary>
        /// <param name="minimumSegment">Minimum requested segment to return.</param>
        /// <param name="bytes">Number of bytes requested.</param>
        /// <returns>Starting segment of the requested block of memory.</returns>
        public ushort Allocate(ushort minimumSegment, int bytes)
        {
            if(bytes <= 0)
                throw new ArgumentOutOfRangeException("bytes");

            uint paragraphs = (uint)(bytes >> 4);
            if((bytes % 16) != 0)
                paragraphs++;

            lock(this.allocations)
            {
                Allocation freeBlock;
                try
                {
                    freeBlock = this.allocations.Where(a => !a.IsUsed && InRange(a, minimumSegment, paragraphs)).First();
                }
                catch(InvalidOperationException ex)
                {
                    throw new InvalidOperationException("Not enough conventional memory.", ex);
                }

                if(freeBlock.Length == paragraphs)
                {
                    freeBlock.IsUsed = true;
                    return freeBlock.Segment;
                }

                var providedSegment = Math.Max(minimumSegment, freeBlock.Segment);

                var newFreeBlockA = new Allocation(freeBlock.Segment, (uint)providedSegment - (uint)freeBlock.Segment, false);
                var newUsedBlock = new Allocation(providedSegment, paragraphs, true);
                var newFreeBlockB = new Allocation((ushort)(providedSegment + paragraphs), freeBlock.Length - newFreeBlockA.Length - paragraphs, false);

                var newBlocks = new List<Allocation>(3);
                if(newFreeBlockA.Length > 0)
                    newBlocks.Add(newFreeBlockA);
                newBlocks.Add(newUsedBlock);
                if(newFreeBlockB.Length > 0)
                    newBlocks.Add(newFreeBlockB);

                this.allocations.Replace(freeBlock, newBlocks.ToArray());

                return newUsedBlock.Segment;
            }
        }
        /// <summary>
        /// Returns the size of the largest free block of memory.
        /// </summary>
        /// <returns>Size in bytes of the largest free block of memory.</returns>
        public uint GetLargestFreeBlockSize()
        {
            lock(this.allocations)
            {
                return this.allocations.Where(a => !a.IsUsed).Max(a => a.Length) << 4;
            }
        }
        #endregion

        #region Private Static Methods
        /// <summary>
        /// Returns a value indicating whether an allocation contains an address range.
        /// </summary>
        /// <param name="a">Allocation to test.</param>
        /// <param name="segment">Minimum requested segment address.</param>
        /// <param name="length">Requested allocation length.</param>
        /// <returns>True if allocation is acceptable; otherwise false.</returns>
        private static bool InRange(Allocation a, ushort segment, uint length)
        {
            if(a.Segment + a.Length >= segment + length)
                return true;

            if(a.Segment >= segment && a.Length >= length)
                return true;

            return false;
        }
        #endregion

        /// <summary>
        /// Describes a conventional memory allocation.
        /// </summary>
        private sealed class Allocation : IEquatable<Allocation>
        {
            #region Constructors
            /// <summary>
            /// Initializes a new instance of the Allocation class.
            /// </summary>
            /// <param name="segment">The starging segment of the allocation.</param>
            /// <param name="length">The length of the allocation in 16-byte paragraphs.</param>
            /// <param name="isUsed">Indicates whether the allocation is in use or a free block.</param>
            public Allocation(ushort segment, uint length, bool isUsed)
            {
                this.Segment = segment;
                this.Length = length;
                this.IsUsed = isUsed;
            }
            #endregion

            #region Public Fields
            /// <summary>
            /// The starting segment of the allocation.
            /// </summary>
            public ushort Segment;
            /// <summary>
            /// Indicates whether the allocation is in use or a free block.
            /// </summary>
            public bool IsUsed;
            /// <summary>
            /// The length of the allocation in 16-byte paragraphs.
            /// </summary>
            public uint Length;
            #endregion

            #region Public Methods
            /// <summary>
            /// Tests for value equality with another instance.
            /// </summary>
            /// <param name="other">Other instance to test for value equality.</param>
            /// <returns>True if objects are equal; otherwise false.</returns>
            public bool Equals(Allocation other)
            {
                if(other == null)
                    return false;

                return this.Segment == other.Segment && this.IsUsed == other.IsUsed && this.Length == other.Length;
            }
            /// <summary>
            /// Tests for value equality with another instance.
            /// </summary>
            /// <param name="obj">Other instance to test for value equality.</param>
            /// <returns>True if objects are equal; otherwise false.</returns>
            public override bool Equals(object obj)
            {
                return Equals(obj as Allocation);
            }
            /// <summary>
            /// Returns a hash code for the instance.
            /// </summary>
            /// <returns>Hash code for the instance.</returns>
            public override int GetHashCode()
            {
                return this.Segment;
            }
            /// <summary>
            /// Returns a string representation of the allocation.
            /// </summary>
            /// <returns>String representation of the allocation.</returns>
            public override string ToString()
            {
                return string.Format("{0:X4}: {1}", this.Segment, this.Length);
            }
            #endregion
        }
    }
}
